A. Field of the Invention
This invention generally relates to garbage collection for computer systems and, more particularly, to a methodology for determining the existence of reference conflicts in Java bytecodes and for modifying the bytecodes to eliminate the conflicts, thereby improving the performance of garbage collection.
B. Description of the Related Art
An important concept in memory management of computer systems is the way in which memory is allocated to a task, deallocated, and then reclaimed. Memory deallocation and reclamation may be explicit and controlled by an executing program, or may be carried out by another special purpose program which locates and reclaims memory which is unused, but has not been explicitly deallocated. "Garbage collection" is the term used to refer to a class of algorithms used to carry out memory management, specifically, automatic reclamation. There are many known garbage collection algorithms, including reference counting, mark-sweep, and generational garbage collection algorithms. These, and other garbage collection techniques, are described in detail in a book entitled "Garbage Collection, Algorithms For Automatic Dynamic Memory Management" by Richard Jones and Raphael Lins, John Wiley & Sons, 1996. Unfortunately, many of the described techniques for garbage collection have specific requirements which cause implementation problems.
The Java.TM. programming language is an object-oriented programming language that is described, for example, in a text entitled "The Java Language Specification" by James Gosling, Bill Joy, and Guy Steele, Addison-Wesley, 1996. This language is typically compiled to a universal executable format, using a "bytecode instruction set," which can be executed on any platform supporting the Java virtual machine (JVM). The JVM is described, for example, in a text entitled "The Java Virtual Machine Specification," by Tim Lindholm and Frank Yellin, Addison Wesley, 1996.
The JVM may stop an executing program at many bytecode boundaries to execute a garbage collector and optimize memory management in accordance with the collector's algorithm. The difficulty with this scheme, however, is providing accurate information for garbage collection at all points where collection is required.
In an object-oriented system, such as one or more related programs written in Java, a "class" provides a template for the creation of "objects" (which represent items or instances manipulated by the system) having characteristics of that class. The term template denotes that the objects (i.e., data items) in each class, share certain characteristics or attributes determined by the class. Objects are typically created dynamically during system operation. Methods associated with a class generally operate on the objects of the same class.
An object may be located by a "reference," or a small amount of information that can be used to access the object. One way to implement a reference is by means of a "pointer" or "machine address," which uses multiple bits of information, however, other implementations are possible. Objects can themselves contain primitive data items, such as integers or floating point numbers, and/or references to other objects. In this manner, a chain of references can be created, each reference pointing to an object which, in turn, points to another object.
Garbage collection algorithms generally determine reachability of objects from the references held in some set of roots. When an object is no longer reachable, the memory that the object occupies can be reclaimed and reused even if it has not been explicitly deallocated by the program. To be effective, garbage collection techniques should be able to, first, identify references that are directly accessible to the executing program, and, second, given the reference to an object, identify references contained within that object, thereby allowing the garbage collector to transitively trace chains of references.
In most language implementations, stacks form one component of the root set. A stack is a region of memory in which stack frames may be allocated and deallocated. In typical object-oriented systems, each method executing in a thread of control allocates a stack frame, and uses the slots of that stack to hold the values of local variables. Some of those variables may contain references to heap-allocated objects. Such objects must be considered reachable as long as the method is executing. The term stack is used because the stack frames obey a last-in/first-out allocation discipline within a given thread of control. There is generally a stack associated with each thread of control.
A garbage collector may be exact or conservative in how it treats different sources of references, such as stacks. A conservative collector knows only that some region of memory (e.g., a slot in the stack frame) may contain references, but does not know whether or not a given value in that region is a reference. If such a collector encounters a value that is a possible reference value, it must keep the referenced object alive. Because of the uncertainty in recognizing references, the collector is constrained not to move the object, since that would require updating the reference, which might actually be an unfortunately-valued integer or floating-point number. The main advantage of conservative collection is that it allows garbage collection to be used with systems not originally designed to support collection. For example, the collectors described in Bartlett, Joel F., mostly-Copying Collection Picks Up Generations and C++, Technical Report TN-12, DEC Western Research Laboratory, October 1989, and Boehm, Hans Juergen and Weiser, Mark, Garbage Collection in an Uncooperative Environment. Software-Practice & Experience, 18(9), p. 807-820, September 1988, use conservative techniques to support collection for C and C++programs.
In contrast, a collector is exact in its treatment of a memory region if it can accurately distinguish references from non-reference values in that region. Exactness has several advantages over conservatism. A conservative collector may retain garbage referenced by a non-reference value that an exact collector would reclaim. Perhaps more importantly, an exact collector is free to relocate objects referenced only by exactly identified references. In an exact system, one in which references and non-references can be distinguished everywhere, this enables a wide range of useful and efficient garbage-collection techniques that cannot easily be used in a conservative setting.
However, a drawback of exact systems is that they must provide the information that makes them exact, i.e., information on whether a given value in memory is a reference or a primitive value. This may introduce both performance and complexity overhead. For purposes of this description, "val" is used to refer to a primitive data item, such as an integer or a floating point number, that does not function as a reference ("ref").
One technique for providing information distinguishing references from primitive values in exact systems is "tagging," in which values are self-describing: one or more bits in each value is reserved to indicate whether the value is a reference. The MIT LISP Machine was one of the first architectures which used garbage collection and had a single stack with explicitly tagged memory values. Its successor, the Symbolics 3600, commercially available from Symbolics Inc., Cambridge, Mass., also used explicitly tagged memory values.
If tagging is not used, then the system must associate data structures with each memory region allowing references and non-references to be distinguished in that region. For example, each object may start with a reference to a descriptor of the type of the object, which would include a "layout map" describing which fields of the object contain references. Stack frames also contain references, and if the JVM were to offer exact garbage collection it must be able to distinguish slots in the frame assigned to variables that contain references from those that contain primitive values. A "stack map" is a data structure that, for each execution point at which a collection may occur, indicates which slots in the stack frame contain references.
The layout map of an object is associated with the object type such that all objects of a given type have the same layout map, and the map of an object is the same for its entire lifetime. In contrast, the layout of a stack frame may change during its lifetime. A given stack frame slot may be uninitialized at the start of a method, hold a reference for one block in the method, then hold an integer for another block. This introduces certain difficulties in relying on the stack maps for determining appropriate garbage collection points.
For example, a compiler may translate a program fragment of a method such that two variables, one representing a primitive value and the other representing a reference, are mapped to the same slot in the stack frame. In fact, whether a given stack frame slot contains a reference at a given point in a method execution may depend not only on the current point in the program execution but also on the control path leading to that point. Along one control path, the stack frame slot might be assigned a primitive value, while along another path the same slot might be assigned a reference. That fact that there are two possibilities makes it impossible to use a stack map to determine the stack layout at garbage collection points.
In general, program code written in the Java language is compiled by a Java compiler, and the compiled program consists of the bytecodes that are executed by the JVM. However, not all Java programs need go through the same compiler. Moreover, it is possible to construct a bytecode program directly, using tools such as "Java assemblers," bypassing a compiler altogether. Thus, Java source code is not the exclusive source of bytecodes executable by the JVM. Consequently, the JVM Specification lays out a set of rules defining well-formed Java class files, along with a description of a procedure called the "bytecode verifier" for checking adherence to those rules. According to one of these rules, the verifier rejects instructions that do not satisfy predetermined constraints. For example, the iadd bytecode causes the JVM to pop the top two elements of the operand stack used for method execution, add the values together, and push the result on the top of the operand stack. However, the verifier knows that the iadd bytecode constraint requires that the top two elements on the operand stack be integers. If the verifier cannot prove that a method in a class file pushes two integers on the operand stack before executing an iadd instruction, the verifier will reject that class file.
Consider the case of a method that has two control paths leading to the same instruction I, which uses some local (i.e., stack-allocated) variable v. If I places some constraint on v, the verifier must prove that this constraint is met no matter which control path reaches I. Thus, when two control paths join at a common instruction, the verifier must show that subsequent constraints on variables such as v are satisfied assuming only the least general type for v that describes the value assigned along both control paths. This least general type describing both possible types of v is called the "merge" of its types along the two paths.
The JVM explicitly allows one exception to this control path rule to accommodate the Java bytecode instruction set for a pair of operations called jsr and ret. The jsr insthiction jumps to an address specified in the instruction and pushes a return address value (i.e., the address of the instruction immediately following the jsr) on the operand stack of the current method. The ret instruction specifies a local variable that must contain a return address, and jumps to that return address. The intended use of these bytecodes is in the implementation of the EQU try {body} finally {handler}
construct of the Java language, in which the instructions included in the finally's handler are executed no matter how the try's body is exited. The Java compiler translates the handler as a jsr subroutine within the method. Every instruction that exits try's body, such as a return statement (when the bytecodes for body are completed normally) or throw statement (when the bytecodes for body "throw" an exception representing an error condition to be handled by a "universal error handler"), are preceded in the translation by a jsr to that subroutine, which would store the pushed return address in a local variable, perform the work of the handler, then perform a ret. Although a jsr subroutine resembles a real method, there is a crucial difference: it executes in the same stack frame as its containing method and has access to all the local variables of this method.
According to the exception for verification of jsr subroutines, the bytecode verifier permits a local variable v that is neither read nor written in a jsr to retain its type across a jsr to that subroutine. This exception causes difficulty for implementing exact garbage collection in the JVM.
Consider the case shown in FIG. 1 in which there are two jsr's, one from PATH A and a second from PATH B, leading to the same jsr subroutine C. At the jsr from PATH A, a local variable r.sub.3 is used to hold an integer value (7), and at the other jsr from PATH B, r.sub.3 holds a reference (to a location holding the string "HI"). Assume that the jsr subroutine C does not use r3 in any way. In this case, the exception forjsr subroutines allows each of PATH A and PATH B to assume that r3 is of the appropriate type for its use after return from the jsr. However, should a garbage collection occur at gc point while a thread is in the jsr subroutine C, the JVM is unable to determine from the stack map whether r.sub.3 contains a reference. Thus, the path leading to the subroutine constitutes the determinative factor for the contents of r.sub.3. If r.sub.3 contains a reference then the garbage collector must process it as a reference; otherwise, it should ignore r.sub.3. Similarly, as shown in FIG. 2, the stack map is unclear as to the contents of r.sub.3 ; from PATH B the variable contains a reference but from PATH A the variable is not initialized.
Simply ignoring these conflicts (i.e., the ref-val conflict and ref-uninit conflict) by disallowing garbage collections for the duration of the jsr subroutine is not an option since try-finally handlers can perform arbitrary computation, including calling methods that may execute indefinitely and allocate an unbounded number of objects. Accordingly, there is a need for a technique to eliminate the ref-val and ref-uninit conflicts associated with bytecodes defining two control paths leading to the same sequence of instructions, such as a subroutine, where it is generally not possible to determine whether a variable contains a reference during execution of the subroutine due to the existence of either type of conflict.